#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
#include <cmath>
#include <unordered_map>

using namespace std;

template<typename T>
bool cmp(T a, T b)
{
    return a<b;
}


template<class T>
class Treenode
{
public:
    T val;
    Treenode<T>* left;
    Treenode<T>* right; 
public:
    Treenode() : val(0), left(nullptr), right(nullptr){}
    Treenode(T value) : val(value), left(nullptr), right(nullptr){}
    ~Treenode()
    {
        if(this->left!=nullptr)
            delete left;
        if(this->right!=nullptr)
            delete right;
    }
};

template<class T>
class Tree
{
public:
    Treenode<T>* root;
public:
    Tree() : root(nullptr){}
    ~Tree()
    {
        if(root!=nullptr)
            delete root;
    }

    void insert(T value)
    {
        Treenode<T>* newnode = new Treenode<T>(value);
        if(root == nullptr) root = newnode;
        else
        {
            Treenode<T>* tmp = root;
            while(tmp!=nullptr)
            {
                if(cmp(value, tmp->val))
                {
                    if(tmp->left != nullptr)
                        tmp = tmp->left;
                    else
                    {
                        tmp->left = newnode;
                        break;
                    }
                }
                else
                {
                    if(tmp->right != nullptr)
                        tmp = tmp->right;
                    else
                    {
                        tmp->right = newnode;
                        break;
                    }

                }
            }
        }
    }

    vector<T> preorderTree(void)
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        if(this->root == nullptr) return resault;
        sta.push(this->root);
        while(!sta.empty())
        {
            Treenode<T>* node = sta.top();
            sta.pop();
            resault.emplace_back(node->val);
            if(node->right) sta.push(node->right);
            if(node->left) sta.push(node->left);
        }

        return resault;

    }

    vector<T> inorderTree(void)
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        Treenode<T>* cur;
        if(this->root == nullptr) return resault;
        cur = this->root;
        while(cur!=nullptr || !sta.empty())
        {
            if(cur != nullptr)
            {
                sta.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = sta.top();
                sta.pop();
                resault.emplace_back(cur->val);
                cur = cur->right;
            }
            

        }

        return resault;
    }

    vector<T> postorderTree(void)
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        if(this->root == nullptr) return resault;
        sta.push(this->root);
        while(!sta.empty())
        {
            Treenode<T>* node = sta.top();
            sta.pop();
            resault.emplace_back(node->val);
            if(node->left) sta.push(node->left);
            if(node->right) sta.push(node->right);

        }
        reverse(resault.begin(), resault.end());
        return resault;

    }


    vector<T> preorderTraverNull()
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        if(this->root!=nullptr) sta.push(this->root);
        while(!sta.empty())
        {
            Treenode<T>* node = sta.top();
            if(node != nullptr)
            {
                sta.pop();
                if(node->right) sta.push(node->right);
                if(node->left) sta.push(node->left);
                sta.push(node);
                sta.push(nullptr);
            }
            else
            {
                sta.pop();
                node = sta.top();
                resault.emplace_back(node->val);
                sta.pop();
            }

        }

        return resault;
    }




    vector<T> inorderTraverNull()
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        if(this->root != nullptr) sta.push(this->root);
        while(!sta.empty())
        {
            Treenode<T>* node = sta.top();
            if(node!=nullptr)
            {
                sta.pop();
                if(node->right) sta.push(node->right);
                sta.push(node);
                sta.push(nullptr);
                if(node->left) sta.push(node->left);
            }
            else
            {
                sta.pop();
                node = sta.top();
                resault.emplace_back(node->val);
                sta.pop();
            }
        }

        return resault;
    }

    vector<T> postorderTraverNull()
    {
        stack<Treenode<T>*> sta;
        vector<T> resault;
        if(this->root!=nullptr) sta.push(this->root);
        while(!sta.empty())
        {
            Treenode<T>* node = sta.top();
            if(node!=nullptr)
            {
                sta.push(nullptr);
                if(node->right) sta.push(node->right);
                if(node->left) sta.push(node->left);
            }
            else
            {
                sta.pop();
                node = sta.top();
                resault.emplace_back(node->val);
                sta.pop();
            }
        }

        return resault;
    }

    vector<T> levelOrder(void)
    {
        queue<Treenode<T>*> que;
        vector<T> resault;
        if(this->root != nullptr) que.push(this->root);
        while(!que.empty())
        {
            Treenode<T>* node = que.front();
            resault.emplace_back(node->val);
            que.pop();
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }

        return resault;
    }

    vector<vector<T>> levelOrderPlus(void)
    {
        queue<Treenode<T>*> que;
        vector<vector<T>> resault;
        
        if(this->root != nullptr) que.push(this->root);
        
        while(!que.empty())
        {
            int size = que.size();
            vector<T> tmp;
            for(int i=0; i<size; i++)
            {
                Treenode<T>* node = que.front();
                tmp.emplace_back(node->val);
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }

            resault.emplace_back(tmp);
        }

        return resault;
    }

};

template<class T>
class HuffmanNode
{
public:
    T data;
    int freq;
    HuffmanNode<T>* left;
    HuffmanNode<T>* right;
public:
    HuffmanNode() : freq(0), left(nullptr), right(nullptr){}
    HuffmanNode(int freq) : freq(freq), left(nullptr), right(nullptr){}
    HuffmanNode(T data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr){}
    ~HuffmanNode(){}
};

template<class T>
struct Compare
{
    bool operator()(HuffmanNode<T>* a, HuffmanNode<T>* b)
    {
        return a->freq > b->freq;
    }
};



template<class T>
class HuffmanTree
{
public:
    HuffmanNode<T>* root;
public:
    HuffmanTree(){}
    HuffmanTree(const unordered_map<T, int>& freqMap)
    {
        priority_queue<HuffmanNode<T>*, vector<HuffmanNode<T>*>, Compare<T>> minHeap;
        for(auto pair : freqMap)
            minHeap.push(new HuffmanNode<T>(pair.first, pair.second));
        
        while(minHeap.size()>1)
        {
            HuffmanNode<T>* left = minHeap.top(); minHeap.pop();
            HuffmanNode<T>* right = minHeap.top(); minHeap.pop();
            HuffmanNode<T>* tmp = new HuffmanNode<T>(left->freq+right->freq);
            tmp->left = left;
            tmp->right = right;
            minHeap.push(tmp);
        }

        this->root = minHeap.top();
    }
    ~HuffmanTree(){}

    void printTree()
    {
        stack<HuffmanNode<T>*> sta;
        if(this->root != nullptr) sta.push(this->root);
        while(!sta.empty())
        {
            HuffmanNode<T>* node = sta.top();
            if(node!=nullptr)
            {
                sta.push(nullptr);
                if(node->right) sta.push(node->right);
                if(node->left) sta.push(node->left);
            }
            else
            {
                sta.pop();
                node = sta.top();
                sta.pop();
                printf("%d ", node->freq);
            }
        }
        printf("\n");

    }


};










int main(){
    vector<int> data = {1,2,3,4,5};
    vector<int> freq = {1,2,3,4,5};
    unordered_map<int, int> freqMap;
    for(int i=0; i<data.size(); i++)
    {
        freqMap.emplace(data[i], freq[i]);
    }
    HuffmanTree<int>* tree = new HuffmanTree<int>(freqMap);
    tree->printTree();
    

    return 0;
}

